package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*

 https://leetcode.cn/problems/binary-tree-paths/description/
 https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

257. 二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：
输入：root = [1]
输出：["1"]
 */
class leetcode_257 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n5 = TreeNode(5)

        n1.left = n2
        n1.right = n3
        n2.right = n5
        val actual = binaryTreePaths(n1)
        val expect = arrayListOf("1->2->5", "1->3")
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val actual = binaryTreePaths(n1)
        val expect = arrayListOf("1")
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    private fun binaryTreePaths(root: TreeNode?): List<String> {
//        return binaryTreePaths1(root)
        return binaryTreePaths2(root)
    }

    fun binaryTreePaths1(root: TreeNode?): List<String> {
        /**
         * 题型：二叉树的前序遍历
         *
         * 思路：
         * 当左右孩子为空时，收集节点
         *
         * 时间复杂度：O(N)
         *
         * 空间复杂度：O(N)
         */
        val result : ArrayList<String> = ArrayList()
        collect(root,"", result)
        return result
    }

    fun collect(root: TreeNode?, path: String, result: ArrayList<String>){
        // 1 确认函数参数以及返回值
        // 2 确认终止条件
        if(null == root){
            return
        }
        // 3 确认单次递归的出路逻辑：前序遍历
        // 中
        var path : String = path
        if(path == ""){
            path = "" + root.`val`
        }
        else{
            path = path + "->" + root.`val`
        }

        // 收集节点
        if(root.left == null && root.right == null){
            result.add(path)
            return
        }

        // 左
        collect(root.left, path, result)

        // 右
        collect(root.right, path, result)
    }

    private fun binaryTreePaths3(root: TreeNode?): List<String> {
        if (null == root) {
            return ArrayList<String>()
        }
        val result: ArrayList<String> = ArrayList<String>()
        getPath(root, path = ArrayList<Int>(), result)
        return result
    }

    private fun getPath(root: TreeNode?, path: ArrayList<Int>, result: ArrayList<String>) {
        // 深度遍历，前序遍历，递归
        // 1 确认函数参数以及返回值
        // 2 确认终止条件
        if (null == root) {
            return
        }
        // 3 确认单次递归的出路逻辑：前序遍历
        // 中
        path.add(root.`val`)
        if (null == root.left && root.right == null) {
            var str: String = ""
            for (n in path) {
                if (str == "") {
                    str += n
                } else {
                    str = "$str->$n"
                }
            }
            result.add(str)
            return
        }

        // 左
        if (null != root.left) {
            getPath(root.left, path, result)
            path.removeAt(path.size - 1)
        }

        // 右
        if (null != root.right) {
            getPath(root.right, path, result)
            path.removeAt(path.size - 1)
        }
    }

    private fun binaryTreePaths2(root: TreeNode?): List<String> {
        // 深度遍历 - 前序 中左右 - 迭代
        // 栈 - 右 左  中
        // T - N
        // S - N

        val list: ArrayList<String> = ArrayList<String>()
        if (null == root) {
            return list
        }

        val stack: LinkedList<Triple<TreeNode, String, Boolean>> = LinkedList<Triple<TreeNode, String, Boolean>>()
        stack.push(Triple<TreeNode, String, Boolean>(root, "" + root.`val`, false))

        while (!stack.isEmpty()) {
            val pair: Triple<TreeNode, String, Boolean> = stack.pop()
            val node: TreeNode = pair.first
            val path: String = pair.second
            val visited: Boolean = pair.third

            if (visited) {
                if (node.left == null && node.right == null) {
                    list.add(path)
                }
                continue
            }

            // 右
            node.right?.let { stack.push(Triple<TreeNode, String, Boolean>(it, path + "->" + it.`val`, false)) }
            // 左
            node.left?.let { stack.push(Triple<TreeNode, String, Boolean>(it, path + "->" + it.`val`, false)) }
            // 中
            stack.push(Triple<TreeNode, String, Boolean>(node, path, true))
        }
        return list
    }
}